package homework.exp04;

import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.Scanner;
import java.util.Stack;

/**
 * B3类 - 使用LL(1)分析法实现的语法分析器
 * 基于LL(1)分析表进行非递归的语法分析，是一种更通用的语法分析方法
 */
public class B3 {
    // 输入扫描器，用于读取输入数据
    static Scanner cin = null;

    // 静态初始化块：尝试从文件读取输入，失败则使用标准输入
    static {
        try {
            cin = new Scanner(new FileReader(new File("F.in")));
        } catch (IOException e) {
            cin = new Scanner(System.in);
        }
    }

    // 终结符集合 (p-z, N, C, D, E, I)，顺序对应分析表列索引
    // 终结符是语言中不能再分解的基本符号
    private static final String VT = "pqrstuvwxyzNCDEI";
    // 非终结符集合 (仅S，开始符号)
    // 非终结符表示语法结构，可以进一步分解
    private static final String VN = "S";

    // LL(1)分析表：行=非终结符(S)，列=终结符索引，值=产生式
    // LL(1)表定义了在特定非终结符和当前输入符号下应选择的产生式
    static String[][] LL1_TABLE = {
            // 列顺序：p q r s t u v w x y z N C D E I #
            { "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "NS", "CSS", "DSS", "ESS", "ISS", "null" }
    };

    /**
     * 主方法：读取每一行输入并调用LL(1)分析方法
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        while (cin.hasNextLine()) {
            String input = cin.nextLine().trim();
            if (parse(input)) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
        cin.close();
    }

    /**
     * LL(1)语法分析主方法 - 根据文法S->p|q|r|s|t|u|v|w|x|y|z|NS|DSS|CSS|ISS|ESS实现
     * 使用栈和LL(1)分析表进行非递归的自顶向下语法分析
     * 
     * @param input 待分析的输入字符串
     * @return 是否符合语法规则
     */
    private static boolean parse(String input) {
        // 创建分析栈，用于存储待匹配的符号
        Stack<Character> stack = new Stack<>();
        // 初始栈状态：先压入结束符#，再压入开始符号S
        stack.push('#');
        stack.push('S');
        // 为输入字符串追加结束符#
        String s = input + "#";
        int currentIndex = 0; // 当前处理的输入字符位置
        int n = s.length();

        // 分析循环，直到处理完所有输入字符
        while (currentIndex < n) {
            // 栈为空表示分析失败
            if (stack.isEmpty())
                return false;

            // 弹出栈顶符号
            char top = stack.pop();
            // 获取当前输入字符
            char currentChar = s.charAt(currentIndex);

            // 处理结束符
            if (top == '#') {
                // 只有当当前字符也是结束符且是最后一个字符时才匹配成功
                return currentChar == '#' && currentIndex == n - 1;
            }

            // 当前栈顶是终结符，直接进行匹配
            if (VT.indexOf(top) != -1) {
                if (top == currentChar) {
                    // 匹配成功，移动输入指针到下一个字符
                    currentIndex++;
                } else {
                    // 终结符不匹配，分析失败
                    return false;
                }
            }
            // 当前栈顶是非终结符，查询LL(1)表获取应使用的产生式
            else if (VN.indexOf(top) != -1) {
                // 计算非终结符在LL(1)表中的行索引
                int ntIndex = VN.indexOf(top); // 非终结符S的索引为0
                // 计算当前输入字符在LL(1)表中的列索引
                int tIndex = VT.indexOf(currentChar);

                // 检查是否为非法字符或无对应的产生式
                if (tIndex == -1 || ntIndex == -1 || "null".equals(LL1_TABLE[ntIndex][tIndex])) {
                    return false;
                }

                // 获取应使用的产生式
                String production = LL1_TABLE[ntIndex][tIndex];
                // 产生式逆序入栈（因为栈是后进先出）
                for (int i = production.length() - 1; i >= 0; i--) {
                    stack.push(production.charAt(i));
                }
            } else {
                // 遇到非法符号
                return false;
            }
        }
        // 所有字符处理完毕后，栈应包含结束符#
        return stack.isEmpty();
    }
}
